Pionek [B]

Limit pamięci: 192 MB

Rosnąca popularność bajtockich szachów spowodowała, że powstało wiele odmian tej gry. Ponieważ w tradycyjnej postaci gra toczy się na nieskończonej planszy, co bywa kłopotliwe, czasem gra się w uproszczone wersje, w których rozmiary plansz ograniczone są przez . Niektóre pola planszy są czarne, zaś pozostałe - białe, jednak sposób pokolorowania pól zależy od konkretnej planszy. Pionek porusza się na tej planszy w nieco inny sposób niż w szachach klasycznych - w każdym ruchu może się on przesunąć w pionie, w poziomie lub na skos na dowolne spośród ośmiu sąsiednich pól, o ile jest ono tego samego koloru co pole, na którym się aktualnie znajduje.

Przykłady dozwolonych ruchów.

Dla podanych par pól na planszy należy stwierdzić, czy pionek może przejść pomiędzy nimi.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , i (, , ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio rozmiar planszy, liczbę czarnych fragmentów planszy opisanych na wejściu oraz liczbę zapytań. Plansza ma wymiary i składa się z pól, których obie współrzędne są z przedziału od do . W kolejnych wierszach znajdują się opisy czarnych obszarów planszy (nie muszą one być koniecznie rozłączne). Każdy z nich składa się z trzech liczb całkowitych , oraz (, ), pooddzielanych pojedynczymi odstępami i oznaczających, że w wierszu pola w kolumnach od do są czarne. Pola planszy, które nie są zawarte w żadnym czarnym obszarze opisanym w wejściu, są białe.

W kolejnych wierszach znajdują się zapytania. Każde zapytanie składa się z dwóch par liczb całkowitych , , , () pooddzielanych pojedynczymi odstępami. Oznaczają one pytanie o możliwość przejścia z pola w wierszu i kolumnie na pole w wierszu i kolumnie .

Wyjście

Na standardowe wyjście należy wypisać wierszy z odpowiedziami na poszczególne zapytania, w takiej samej kolejności, w jakiej występują one na wejściu. Odpowiedź na każde zapytanie to wiersz z napisem "TAK" lub "NIE" (bez cudzysłowów), w zależności od tego, czy pionek może przejść pomiędzy dwoma podanymi polami, nie przechodząc nigdy przez pole innego koloru.

Przykład

Dla danych wejściowych:

4 5 2
1 1 1
2 3 4
3 2 2
4 2 2
4 2 2
1 1 3 2
1 2 4 4

poprawną odpowiedzią jest:

NIE
TAK

Przykładowa plansza wraz z zapytaniami.

Autor zadania: Krzysztof Diks.